import { Comparator, CompareFunction, CompareType } from "../../utils/Comparator";
import { toType } from "../../utils/utils";
import { BinaryTreeNode } from "./BinaryTreeNode";

export class BinarySearchNode<T> extends BinaryTreeNode<T> {

    /** 结点元素比较器 */
    private nodeValueComparator: Comparator<T>;
    /** 比较器函数 */
    private compareFn: CompareFunction<T>;

    constructor (
        element: T,
        compareFn: CompareFunction<T> = null,
        left: BinarySearchNode<T> = null,
        right: BinarySearchNode<T> = null
    ) {
        super(element, left, right);

        this.compareFn = compareFn;
        this.nodeValueComparator = new Comparator(compareFn);
    }

    /** 插入元素 */
    insert (elem: T): BinarySearchNode<T> {
        const ret = this.nodeValueComparator.compare(elem, this.element);
        if (ret === CompareType.EQUAL) {
            // 如果比较结果与当前结点相等，则使用新值替换旧值
            this.element = elem;
            return this;
        } else if (ret === CompareType.LESSER) {
            // 如果比较结果小于当前结点，
            // 如果没有左子结点，则添加到左子结点
            // 否则，添加到左子树
            if (this.left) {
                return toType<BinarySearchNode<T>>(this.left.insert(elem));
            }

            const newNode = new BinarySearchNode(elem, this.compareFn);
            this.left = newNode;

            return newNode;
        } else if (ret === CompareType.GREATER) {
            // 如果比较结果大于当前结点，
            // 如果没有右子结点，则添加到右子结点
            // 否则，添加到右子树
            if (this.right) {
                return toType<BinarySearchNode<T>>(this.right.insert(elem));
            }
            const newNode = new BinarySearchNode(elem, this.compareFn);
            this.right = newNode;
            return newNode;
        }
    }


    /** 删除元素 */
    remove (elem: T): boolean {
        const nodeToRemove = this.find(elem);

        if (!nodeToRemove) {
            throw new Error("Item not fond in the tree");
        }

        const { parent } = nodeToRemove;

        if (nodeToRemove.isLeaf) {
            // 如果删除结点为叶子结点
        } else if (nodeToRemove.left && nodeToRemove.right) {
            // 如果有两个子结点
            // 获取其后继结点，用其替换当前节点
            // 再删除后继结点
            
        }


        return false;
    }

    /** 查找元素 */
    find (elem: T): BinarySearchNode<T> {
        const ret = this.nodeValueComparator.compare(elem, this.element);
        if (ret === CompareType.EQUAL) {
            return this;
        } else if (ret === CompareType.LESSER && this.left) {
            return toType<BinarySearchNode<T>>(this.left.find(elem));
        } else if (ret === CompareType.GREATER && this.right) {
            return toType<BinarySearchNode<T>>(this.right.find(elem));
        }
        return null;
    }

    /** 查找最小结点 */
    findMin (): BinarySearchNode<T> {
        if (!this.left) return this;

        return toType<BinarySearchNode<T>>(this.left.findMin());
    }
}